package 其他;

public class 最长递增子序列个数 {
    public int findNumberOfLIS(int[] nums) {
        int[] dp = new int[nums.length],cut = new int[nums.length];
        int res = 0,maxlen = 1,ans = 0;
        for(int i = 0; i < nums.length; i++){
            dp[i] = 1;
            cut[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        cut[i] = cut[j];
                    }else if(dp[j] + 1 == dp[i]){
                        cut[i] += cut[j];
                    }
                }
            }
            if (dp[i] > maxlen) {
                maxlen = dp[i];
                ans = cut[i];
            }else if(dp[i] == maxlen){
                ans += cut[i];
            }
        }
        return ans;
    }
}
